
use std::rc::Rc;
use std::cell::RefCell;

struct te_variable {
    name: String,
    type_: i32,
}

struct state {
    lookup: Vec<te_variable>,
    lookup_len: usize,
}

pub struct TeExpr {
    pub type_: i32,
    pub value: f64,
    pub bound: Option<Vec<f64>>,
    pub function: Option<fn(Vec<f64>) -> f64>,
    pub parameters: Vec<Rc<RefCell<TeExpr>>>,
}

pub struct State {
    pub start: String,
    pub next: String,
    pub type_: i32,
    pub value: f64,
    pub bound: Option<Vec<f64>>,
    pub function: Option<fn(Vec<f64>) -> f64>,
    pub context: Option<Rc<RefCell<State>>>,
    pub lookup: Vec<te_variable>,
    pub lookup_len: usize,
}

const TOK_NULL: i32 = 0;
const TOK_END: i32 = 1;
const TOK_NUMBER: i32 = 2;
const TOK_ERROR: i32 = 3;
const TOK_VARIABLE: i32 = 4;
const TOK_INFIX: i32 = 5;
const TOK_OPEN: i32 = 6;
const TOK_CLOSE: i32 = 7;
const TOK_SEP: i32 = 8;

const TE_VARIABLE: i32 = 0;
const TE_CLOSURE0: i32 = 1;
const TE_CLOSURE1: i32 = 2;
const TE_CLOSURE2: i32 = 3;
const TE_CLOSURE3: i32 = 4;
const TE_CLOSURE4: i32 = 5;
const TE_CLOSURE5: i32 = 6;
const TE_CLOSURE6: i32 = 7;
const TE_CLOSURE7: i32 = 8;
const TE_FUNCTION0: i32 = 9;
const TE_FUNCTION1: i32 = 10;
const TE_FUNCTION2: i32 = 11;
const TE_FUNCTION3: i32 = 12;
const TE_FUNCTION4: i32 = 13;
const TE_FUNCTION5: i32 = 14;
const TE_FUNCTION6: i32 = 15;
const TE_FUNCTION7: i32 = 16;

const TE_FLAG_PURE: i32 = 0x80000000;
const TE_CONSTANT: i32 = 0x10000000;









pub fn find_builtin(name: String, len: i32, functions: &[te_variable]) -> Option<&te_variable> {
    let mut imin = 0;
    let mut imax = functions.len() - 2;

    while imax >= imin {
        let i = imin + ((imax - imin) / 2);
        let c = name.as_bytes().iter().zip(functions[i].name.as_bytes()).take(len as usize).fold(0, |acc, (a, b)| acc + (*a as i32 - *b as i32));
        let c = if c == 0 { -(functions[i].name.as_bytes()[len as usize] as i32) } else { c };
        if c == 0 {
            return Some(&functions[i]);
        } else if c > 0 {
            imin = i + 1;
        } else {
            imax = i - 1;
        }
    }

    None
}


pub fn new_expr(type_: i32, parameters: Option<Vec<std::rc::Rc<std::cell::RefCell<TeExpr>>>>) -> std::rc::Rc<std::cell::RefCell<TeExpr>> {
    let arity = ARITY(type_);
    let mut expr = std::rc::Rc::new(std::cell::RefCell::new(TeExpr {
        type_: type_,
        value: 0.0,
        bound: None,
        function: None,
        parameters: Vec::new(),
    }));

    if let Some(params) = parameters {
        if params.len() == arity as usize {
            expr.borrow_mut().parameters = params;
        }
    }

    expr
}


pub fn find_lookup<'a>(s: &'a State, name: &str, len: usize) -> Option<&'a te_variable> {
    if s.lookup.is_empty() {
        return None;
    }

    for var in s.lookup.iter().take(s.lookup_len) {
        if var.name.len() == len && var.name == name {
            return Some(var);
        }
    }
    None
}


pub fn mul(a: f64, b: f64) -> f64 {
// 注意：该函数不允许修改，因为工程中其他文件中的函数也调用了他们，如果修改了，会影响其他文件内函数的功能，完整原样返回该函数
    a * b
}


pub fn next_token(s: &mut State) {
    s.type_ = TOK_NULL;

    loop {
        if s.next.is_empty() {
            s.type_ = TOK_END;
            return;
        }

        // Try reading a number.
        if s.next.chars().next().unwrap().is_ascii_digit() || s.next.starts_with('.') {
            s.value = s.next.parse::<f64>().unwrap();
            s.type_ = TOK_NUMBER;
        } else {
            // Look for a variable or builtin function call.
            if s.next.chars().next().unwrap().is_alphabetic() {
                let start = s.next.clone();
                while !s.next.is_empty() && (s.next.chars().next().unwrap().is_alphanumeric() || s.next.starts_with('_')) {
                    s.next.remove(0);
                }

                let var = find_lookup(s, &start, s.next.len());
                if var.is_none() {
                    let var = find_builtin(start, s.next.len() as i32, &s.lookup);
                    if var.is_none() {
                        s.type_ = TOK_ERROR;
                    } else {
                        match var.unwrap().type_ {
                            TE_VARIABLE => {
                                s.type_ = TOK_VARIABLE;
                                s.bound = Some(vec![0.0]);
                            },
                            TE_CLOSURE0 | TE_CLOSURE1 | TE_CLOSURE2 | TE_CLOSURE3 |
                            TE_CLOSURE4 | TE_CLOSURE5 | TE_CLOSURE6 | TE_CLOSURE7 => {
                                s.context = Some(Rc::new(RefCell::new(State {
                                    start: String::new(),
                                    next: String::new(),
                                    type_: 0,
                                    value: 0.0,
                                    bound: None,
                                    function: None,
                                    context: None,
                                    lookup: vec![],
                                    lookup_len: 0,
                                })));
                            },
                            TE_FUNCTION0 | TE_FUNCTION1 | TE_FUNCTION2 | TE_FUNCTION3 |
                            TE_FUNCTION4 | TE_FUNCTION5 | TE_FUNCTION6 | TE_FUNCTION7 => {
                                s.type_ = var.unwrap().type_;
                                s.function = Some(mul_wrap);
                            },
                            _ => {}
                        }
                    }
                }
            } else {
                // Look for an operator or special character.
                match s.next.remove(0) {
                    '+' => { s.type_ = TOK_INFIX; s.function = Some(add_wrap); },
                    '-' => { s.type_ = TOK_INFIX; s.function = Some(sub_wrap); },
                    '*' => { s.type_ = TOK_INFIX; s.function = Some(mul_wrap); },
                    '/' => { s.type_ = TOK_INFIX; s.function = Some(divide_wrap); },
                    '^' => { s.type_ = TOK_INFIX; s.function = Some(mul_wrap); },
                    '%' => { s.type_ = TOK_INFIX; s.function = Some(mul_wrap); },
                    '(' => s.type_ = TOK_OPEN,
                    ')' => s.type_ = TOK_CLOSE,
                    ',' => s.type_ = TOK_SEP,
                    ' ' | '\t' | '\n' | '\r' => {},
                    _ => s.type_ = TOK_ERROR,
                }
            }
        }

        if s.type_ != TOK_NULL {
            break;
        }
    }
}


pub fn te_free(n: Option<std::rc::Rc<std::cell::RefCell<TeExpr>>>) {
    if n.is_none() {
        return;
    }
    let n = n.unwrap();
    te_free_parameters(Some(n.clone()));
}


pub fn sub(a: f64, b: f64) -> f64 { a - b }


pub fn negate(a: f64) -> f64 { -a }


pub fn te_free_parameters(n: Option<std::rc::Rc<std::cell::RefCell<TeExpr>>>) {
    if n.is_none() {
        return;
    }
    let n = n.unwrap();
    let type_mask = n.borrow().type_ & 0x0000001F;
    match type_mask {
        7 | 23 => te_free(Some(n.borrow().parameters[6].clone())),
        6 | 22 => te_free(Some(n.borrow().parameters[5].clone())),
        5 | 21 => te_free(Some(n.borrow().parameters[4].clone())),
        4 | 20 => te_free(Some(n.borrow().parameters[3].clone())),
        3 | 19 => te_free(Some(n.borrow().parameters[2].clone())),
        2 | 18 => te_free(Some(n.borrow().parameters[1].clone())),
        1 | 17 => te_free(Some(n.borrow().parameters[0].clone())),
        _ => (),
    }
}


pub fn divide(a: f64, b: f64) -> f64 {
// 注意：该函数不允许修改，因为工程中其他文件中的函数也调用了他们，如果修改了，会影响其他文件内函数的功能，完整原样返回该函数
    a / b
}


pub fn add(a: f64, b: f64) -> f64 { a + b }


pub fn factor(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let mut ret = power(s)?;

    while s.type_ == TOK_INFIX && s.function == Some(|params: Vec<f64>| pow_wrap(params[0], params[1])) {
        let t = s.function.unwrap();
        next_token(s);
        let p = power(s)?;

        let prev = ret.clone();
        ret = new_expr(TE_FUNCTION2 | TE_FLAG_PURE, Some(vec![prev.clone(), p.clone()]))?;
        ret.borrow_mut().function = Some(t);
    }

    Some(ret)
}


pub fn power(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let mut sign = 1;

    while s.type_ == TOK_INFIX && (s.function == Some(add_wrap) || s.function == Some(sub_wrap)) {
        if s.function == Some(sub_wrap) {
            sign = -sign;
        }
        next_token(s);
    }

    if sign == 1 {
        base(s)
    } else {
        let b = base(s)?;
        let ret = new_expr(TE_FUNCTION1 | TE_FLAG_PURE, Some(vec![b.clone()]))?;
        ret.borrow_mut().function = Some(negate);
        Some(ret)
    }
}


pub fn term(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let mut ret = factor(s)?;

    while s.type_ == TOK_INFIX && (s.function == Some(mul_wrap) || s.function == Some(divide_wrap) || s.function == Some(fmod_wrap)) {
        let t = s.function.unwrap();
        next_token(s);
        let f = factor(s)?;

        let prev = ret.clone();
        ret = new_expr(TE_FUNCTION2 | TE_FLAG_PURE, Some(vec![prev.clone(), f.clone()]))?;
        ret.borrow_mut().function = Some(t);
    }

    Some(ret)
}


pub fn expr(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let mut ret = term(s)?;

    while s.type_ == TOK_INFIX && (s.function == Some(add_wrap) || s.function == Some(sub_wrap)) {
        let t = s.function.unwrap();
        next_token(s);
        let te = term(s)?;

        let prev = ret.clone();
        ret = new_expr(TE_FUNCTION2 | TE_FLAG_PURE, Some(vec![prev.clone(), te.clone()]))?;
        ret.borrow_mut().function = Some(t);
    }

    Some(ret)
}


pub fn base(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let ret: Rc<RefCell<TeExpr>>;
    let arity: i32;

    match TYPE_MASK(s.type_) {
        TOK_NUMBER => {
            ret = new_expr(TE_CONSTANT, None)?;
            ret.borrow_mut().value = s.value;
            next_token(s);
        },
        TOK_VARIABLE => {
            ret = new_expr(TE_VARIABLE, None)?;
            ret.borrow_mut().bound = s.bound.clone();
            next_token(s);
        },
        TE_FUNCTION0 | TE_CLOSURE0 => {
            ret = new_expr(s.type_, None)?;
            ret.borrow_mut().function = s.function;
            if IS_CLOSURE(s.type_) {
                ret.borrow_mut().parameters.push(Rc::new(RefCell::new(TeExpr {
                    type_: 0,
                    value: 0.0,
                    bound: None,
                    function: None,
                    parameters: Vec::new(),
                })));
            }
            next_token(s);
            if s.type_ == TOK_OPEN {
                next_token(s);
                if s.type_ != TOK_CLOSE {
                    s.type_ = TOK_ERROR;
                } else {
                    next_token(s);
                }
            }
        },
        TE_FUNCTION1 | TE_CLOSURE1 => {
            ret = new_expr(s.type_, None)?;
            ret.borrow_mut().function = s.function;
            if IS_CLOSURE(s.type_) {
                ret.borrow_mut().parameters.push(Rc::new(RefCell::new(TeExpr {
                    type_: 0,
                    value: 0.0,
                    bound: None,
                    function: None,
                    parameters: Vec::new(),
                })));
            }
            next_token(s);
            let p = power(s)?;
            ret.borrow_mut().parameters.push(p);
        },
        TE_FUNCTION2 | TE_FUNCTION3 | TE_FUNCTION4 |
        TE_FUNCTION5 | TE_FUNCTION6 | TE_FUNCTION7 |
        TE_CLOSURE2 | TE_CLOSURE3 | TE_CLOSURE4 |
        TE_CLOSURE5 | TE_CLOSURE6 | TE_CLOSURE7 => {
            arity = ARITY(s.type_);
            ret = new_expr(s.type_, None)?;
            ret.borrow_mut().function = s.function;
            if IS_CLOSURE(s.type_) {
                ret.borrow_mut().parameters.push(Rc::new(RefCell::new(TeExpr {
                    type_: 0,
                    value: 0.0,
                    bound: None,
                    function: None,
                    parameters: Vec::new(),
                })));
            }
            next_token(s);
            if s.type_ != TOK_OPEN {
                s.type_ = TOK_ERROR;
            } else {
                for i in 0..arity {
                    next_token(s);
                    let e = expr(s)?;
                    ret.borrow_mut().parameters.push(e);
                    if s.type_ != TOK_SEP {
                        break;
                    }
                }
                if s.type_ != TOK_CLOSE || ret.borrow().parameters.len() != arity as usize {
                    s.type_ = TOK_ERROR;
                } else {
                    next_token(s);
                }
            }
        },
        TOK_OPEN => {
            next_token(s);
            ret = list(s)?;
            if s.type_ != TOK_CLOSE {
                s.type_ = TOK_ERROR;
            } else {
                next_token(s);
            }
        },
        _ => {
            ret = new_expr(0, None)?;
            s.type_ = TOK_ERROR;
            ret.borrow_mut().value = f64::NAN;
        }
    }

    Some(ret)
}


pub fn comma(a: f64, b: f64) -> f64 { b }


pub fn list(s: &mut State) -> Option<Rc<RefCell<TeExpr>>> {
    let mut ret = expr(s)?;

    while s.type_ == TOK_SEP {
        next_token(s);
        let e = expr(s)?;

        let prev = ret.clone();
        ret = new_expr(TE_FUNCTION2 | TE_FLAG_PURE, Some(vec![prev.clone(), e.clone()]))?;
        ret.borrow_mut().function = Some(comma);
    }

    Some(ret)
}


fn pow_wrap(a: f64, b: f64) -> f64 { a.powf(b) }


fn fmod_wrap(a: f64, b: f64) -> f64 { a % b }


fn main(){}


fn ARITY(type_: i32) -> i32 {
    type_ & 0x0000000F
}


fn mul_wrap(params: Vec<f64>) -> f64 {
    mul(params[0], params[1])
}


fn add_wrap(params: Vec<f64>) -> f64 {
    add(params[0], params[1])
}


fn sub_wrap(params: Vec<f64>) -> f64 {
    sub(params[0], params[1])
}


fn divide_wrap(params: Vec<f64>) -> f64 {
    divide(params[0], params[1])
}

